\subsubsection{Übung vi}

Affin lineare Chiffren kann man über Known-Plaintext-Attacken und das Aufstellen eines linearen Gleichungssystems brechen.

\begin{enumerate}[a)]
\item
Bei dem konkreten Beispiel in \(\text{GF}(2)^2\) kann die Verschlüsselungsfunktion \(x \mapsto Ax + b\) auch geschrieben werden als
\[
 \begin{pmatrix} 
   a_{1,1}     & a_{1,2}\\ 
   a_{2,1}     & a_{2,2} 
 \end{pmatrix}
  \cdot
 \begin{pmatrix} 
   x_1\\ 
   x_2 
 \end{pmatrix}
  +
 \begin{pmatrix} 
   b_1\\ 
   b_2 
 \end{pmatrix}
  =
 \begin{pmatrix} 
   c_1\\ 
   c_2 
 \end{pmatrix}
\]
mit \(a_{i,j}, x_i, b_i, c_i \in \text{GF}(2)\).

Aus \(p  = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, c  = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\) ergibt sich

\begin{align*}
  \begin{pmatrix}
    a_{1,1}     & a_{1,2}\\ 
    a_{2,1}     & a_{2,2}
  \end{pmatrix}
  \cdot
 \begin{pmatrix} 
   0\\ 
   0 
 \end{pmatrix}
  +
 \begin{pmatrix} 
   b_1\\ 
   b_2 
 \end{pmatrix}
  &=
 \begin{pmatrix} 
   1\\ 
   0 
 \end{pmatrix}\\
 \begin{pmatrix} 
   b_1\\ 
   b_2 
 \end{pmatrix}
  &=
 \begin{pmatrix} 
   1\\ 
   0 
 \end{pmatrix}
\end{align*}

Damit ist der Vektor \(b =  
 \begin{pmatrix} 
   1\\ 
   0 
 \end{pmatrix}\) bekannt.
Aus \(p''  = \begin{pmatrix} 0 \\ 1 \end{pmatrix}, c''  = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\) ergibt sich

\begin{align*}
 \begin{pmatrix}
    a_{1,1}     & a_{1,2}\\ 
    a_{2,1}     & a_{2,2}
 \end{pmatrix}
  \cdot
 \begin{pmatrix} 
   0\\ 
   1 
 \end{pmatrix}
  +
 \begin{pmatrix} 
   1\\ 
   0
 \end{pmatrix}
  &=
 \begin{pmatrix} 
   0\\ 
   0 
 \end{pmatrix}\\
 \begin{pmatrix}
    a_{1,1}     & a_{1,2}\\ 
    a_{2,1}     & a_{2,2}
 \end{pmatrix}
  \cdot
 \begin{pmatrix} 
   0\\ 
   1 
 \end{pmatrix}
  &=
 \begin{pmatrix} 
   1\\ 
   0 
 \end{pmatrix}\\
 \Longrightarrow\\
 a_{1,2} &= 1\\
 a_{2,2} &= 0
\end{align*}

Aus \(p'  = \begin{pmatrix} 1 \\ 1 \end{pmatrix}, c'  = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\) ergibt sich

\begin{align*}
 \begin{pmatrix}
    a_{1,1}     & 1\\ 
    a_{2,1}     & 0
 \end{pmatrix}
  \cdot
 \begin{pmatrix} 
   1\\ 
   1 
 \end{pmatrix}
  +
 \begin{pmatrix} 
   1\\ 
   0
 \end{pmatrix}
  &=
 \begin{pmatrix} 
   0\\ 
   1 
 \end{pmatrix}\\
 \begin{pmatrix}
    a_{1,1}     & 1\\ 
    a_{2,1}     & 0
 \end{pmatrix}
  \cdot
 \begin{pmatrix} 
   1\\ 
   1 
 \end{pmatrix}
  &=
 \begin{pmatrix} 
   1\\ 
   1 
 \end{pmatrix}\\
 \Longrightarrow\\
 a_{1,1} &= 0\\
 a_{2,1} &= 1
\end{align*}

Damit ist \(A =  \begin{pmatrix}
    0     & 1\\ 
    1     & 0
 \end{pmatrix}\) und \(b =  \begin{pmatrix} 
   1\\ 
   0
 \end{pmatrix}\).
 
\item
Bei \(\mathcal{P} = \mathcal{C} = \text{GF}(p)^k\), \(p\) prim, \(k \in \mathbb{N}\) gilt für die Verschlüsselungsfunktion \(E_{(A,b)} : \mathcal{P} \rightarrow \mathcal{C}, \: x \mapsto Ax + b\)
die entsprechende Entschlüsselungsfunktion \(D_{(A',b)} : \mathcal{C} \rightarrow \mathcal{P}, \: x \mapsto A'(x - b)\) mit \(A'\) der inversen Matrix von \(A\).

\item
Im Idealfall werden \(k + 1\) \((P,C)\) Paare zur Ermittlung von \(A\) und \(b\) benötigt:\\1 für Vektor \(b\), 1 pro Spalte \(= k\).

\emph{Ausführlicher:} Hat man \(k + 1\) \((P,C)\) Paare, so müssen die Vektoren \((p_i - p_0)\:,\: 1 \le i \le k\) linear unabhängig sein, damit \(A\) bestimmt werden kann (und nicht etwa unterbestimmt ist).\\
\(A\) kann dann durch die \(k\) linearen Gleichungssysteme bestimmt werden, welche durch
\[
 c_i - c_0 = (A \cdot p_i + b) - (A \cdot p_0 + b) = A (p_i - p_0)
\]
gegeben sind. \(b\) kann man dann entsprechend durch Einsetzen des konkreten \(A\) für ein \((P,C)\) Paar ermitteln.

\end{enumerate}
